package 寒假作业.LeetCode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Num496 {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //用单调栈存num2
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0 ; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()){
                stack.pop();
            }
            //把每一个数和自己对应的最大元素放map
            map.put(num,stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] ret = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            //根据num1的值去对应map中的元素
            ret[i] = map.get(nums1[i]);
        }
        return ret;
    }
}
